﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Compilex.BaseLibrary;
using Infraestruturex.Automata;

namespace Compilex.Automata
{
    public class NFA : IAutomaton<NFAState>
    {
        public NFAState StartState { get; set; }
        public IBasicTokenProvider TokenProvider { get; set; }

        private SimpleList<NFAState> currentStates;


        public NFA(NFAState startState)
        {
            this.StartState = startState;
            this.TokenProvider = new SequentialCharsTokenProvider();
        }

        public NFA()
        {
            this.TokenProvider = new SequentialCharsTokenProvider();
        }

        public bool Accepts(String input)
        {
            bool useless;
            return Accepts(input, out useless);
        }

        public bool Accepts(String input, out bool isRecoverable)
        {
            TokenProvider.Input = input;

            currentStates = new SimpleList<NFAState>();
            currentStates.Add(StartState);
            TakeEpsilonTransitions();
            while (TokenProvider.HasMoreTokens() && currentStates.Count > 0)
            {
                TakeRegularTransitions(TokenProvider.PeekNextTokenClass());
                TakeEpsilonTransitions();
                TokenProvider.ConsumeNextToken();
            }

            int acceptStatesCount =
                currentStates.ToArray().Where(s => s.IsAcceptState).Count();
            if (acceptStatesCount > 0)
            {
                isRecoverable = false;
                return true;
            }
            else
            {
                isRecoverable = currentStates.Count > 0;
                return false;
            }
        }

        private void TakeRegularTransitions(string input)
        {
            SimpleList<NFAState> newStates = new SimpleList<NFAState>();
            for (int i = 0; i < currentStates.Count; i++)
            {
                newStates.AddRange(currentStates[i].GetDestinationStates(input));
            }
            currentStates = newStates;
        }

        private void TakeEpsilonTransitions()
        {
            SimpleList<NFAState> newStates = new SimpleList<NFAState>(currentStates);
            for(int i = 0; i < currentStates.Count; i++)
            {
                newStates.AddRange(currentStates[i].GetEpsilonClosure());
            }
            currentStates = newStates;
        }


        public NFAState[] GetStates()
        {
            HashSet<NFAState> states = new HashSet<NFAState>();
            states.Add(this.StartState);
            int lastStateCount;
            do
            {
                lastStateCount = states.Count;
                HashSet<NFAState> newStates = new HashSet<NFAState>();
                foreach (NFAState state in states)
                {
                    for (int i = 0; i < state.Transitions.Count; i++)
                    {
                        newStates.Add(state.Transitions[i].Destination);
                    }
                }
                states.UnionWith(newStates);
            } while (states.Count > lastStateCount);
            return states.ToArray();
        }
    }
}
